package org.everyday;

import cn.hutool.core.lang.Pair;
import com.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Tang World
 * @Date: 27/8/2022 上午10:32
 */
public class L662 {
    public int widthOfBinaryTree(TreeNode root) {
        // 根据编号来计算宽度
        int res = 1;
        List<Pair<TreeNode, Integer>> arr = new ArrayList<Pair<TreeNode, Integer>>();
        arr.add(new Pair<TreeNode, Integer>(root, 1));
        while (!arr.isEmpty()) {
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<Pair<TreeNode, Integer>>();
            for (Pair<TreeNode, Integer> pair : arr) {
                TreeNode node = pair.getKey();
                int order = pair.getValue();
                if (node.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, order * 2));
                }
                if (node.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, order * 2 + 1));
                }
            }
            // 核心代码
            res = Math.max(res, arr.get(arr.size() - 1).getValue() - arr.get(0).getValue() + 1);
            arr = tmp;
        }
        return res;
    }
}
